import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-06-19
 * Time: 8:06
 */
//解法一
class Solution11 {
    List<Integer> path;
    List<List<Integer>> ret;
    int aim;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        aim = target;
        path = new ArrayList<>();
        ret = new ArrayList<>();

        dfs(candidates,0,0);

        return ret;
    }

    void dfs(int[] candidates,int pos,int sum) {
        if(sum == aim) {
            ret.add(new ArrayList<>(path));
            return;
        }

        if(sum > aim || pos == candidates.length) {
            return;
        }

        for(int i = pos; i < candidates.length;i++) {
            path.add(candidates[i]);
            dfs(candidates,i,sum+candidates[i]);
            path.remove(path.size()-1);
        }
    }
}

//解法二
//class Solution {
//    List<Integer> path;
//    List<List<Integer>> ret;
//    int aim;
//
//    public List<List<Integer>> combinationSum(int[] candidates, int target) {
//        aim = target;
//        path = new ArrayList<>();
//        ret = new ArrayList<>();
//
//        dfs(candidates,0,0);
//
//        return ret;
//    }
//
//    void dfs(int[] candidates,int pos,int sum) {
//        if(sum == aim) {
//            ret.add(new ArrayList<>(path));
//            return;
//        }
//
//        if(sum > aim || pos == candidates.length) {
//            return;
//        }
//
//        //解法二 枚举使用个数多少个
//        for(int k = 0; k * candidates[pos] <= aim; k++) {
//            if( k != 0) {
//                path.add(candidates[pos]);
//            }
//            dfs(candidates,pos+1,sum + k * candidates[pos]);
//        }
//        //恢复现场
//        for(int k = 1; k * candidates[pos] <= aim; k++) {
//            path.remove(path.size()-1);
//        }
//
//    }
//}